| 翻訳と辞書 |
| Church's theorem ： ウィキペディア英語版 |
Entscheidungsproblem
In mathematics and computer science, the ''ドイツ語:Entscheidungsproblem'' (, German for 'decision problem') is a challenge posed by David Hilbert in 1928.〔Hilbert and Ackermann〕 The ドイツ語:Entscheidungsproblem asks for an algorithm that takes as input a statement of a first-order logic (possibly with a finite number of axioms beyond the usual axioms of first-order logic) and answers "Yes" or "No" according to whether the statement is ''universally valid'', i.e., valid in every structure satisfying the axioms. By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced from the axioms, so the ドイツ語:Entscheidungsproblem can also be viewed as asking for an algorithm to decide whether a given statement is provable from the axioms using the rules of logic.
In 1936, Alonzo Church and Alan Turing published independent papers〔Church's paper was presented to the American Mathematical Society on 19 April 1935 and published on 15 April 1936. Turing, who had made substantial progress in writing up his own results, was disappointed to learn of Church's proof upon its publication (see correspondence between Max Newman and Church in (Alonzo Church papers )). Turing quickly completed his paper and rushed it to publication; it was received by the ''Proceedings of the London Mathematical Society'' on 28 May 1936, read on 12 November 1936, and published in series 2, volume 42 (1936-7); it appeared in two sections: in Part 3 (pages 230-240), issued on Nov 30, 1936 and in Part 4 (pages 241–265), issued on Dec 23, 1936; Turing added corrections in volume 43(1937) pp. 544–546. See the footnote at the end of Soare:1996.〕 showing that a general solution to the Entscheidungsproblem is impossible, assuming that the intuitive notion of "effectively calculable" is captured by the functions computable by a Turing machine (or equivalently, by those expressible in the lambda calculus). This assumption is now known as the Church–Turing thesis.
== History of the problem ==
The origin of the ドイツ語:Entscheidungsproblem goes back to Gottfried Leibniz, who in the seventeenth century, after having constructed a successful mechanical calculating machine, dreamt of building a machine that could manipulate symbols in order to determine the truth values of mathematical statements.〔Davis 2000: pp. 3–20〕 He realized that the first step would have to be a clean formal language, and much of his subsequent work was directed towards that goal. In 1928, David Hilbert and Wilhelm Ackermann posed the question in the form outlined above.
In continuation of his "program," Hilbert posed three questions at an international conference in 1928, the third of which became known as "Hilbert's ドイツ語:Entscheidungsproblem."〔Hodges p. 91〕 As late as 1930, he believed that there would be no such thing as an unsolvable problem.〔Hodges p. 92, quoting from Hilbert〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Entscheidungsproblem」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|